import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
import java.util.Stack;

public class Leet32 {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("()())()()()"));
    }
    static public int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0,j = -1; i < s.length(); i++)
            if (s.charAt(i)=='(')
                stack.push(i);
            else {
                if (!stack.isEmpty()){
                    stack.pop();
                    max = Math.max(max,i-(stack.isEmpty()?j:stack.peek()));
                }else
                    j = i;
            }
        return max;
    }
}
class Sol1ution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        for (int i = 0, j = -1; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.addLast(i);
            } else {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                    int top = stack.isEmpty()?j:stack.peekLast();
                    ans = Math.max(ans, i - top);
                } else {
                    j = i;
                }
            }
        }
        return ans;
    }
}

